﻿using System;
using Algoritmia.DataStructures.Lists;
using Algoritmia.Utils;

namespace Algoritmia.Problems.Searching
{
    public class RandomizedBinarySearcher<T> : ISortedSearcher<T>
    {
        private Comparison<T> _comparison;
        private readonly Random _r;

        public RandomizedBinarySearcher()
        {
            _r = new Random();
        }

        public int IndexOf(IList<T> list, T elem, Comparison<T> comparison = null)
        {
            _comparison = AlgoritmiaFactory.GetDefaultComparison(comparison);
            Func<int, int, int> f = null;
            f = (i, k) =>
                    {
                        if (k - i <= 1)
                        {
                            if (_comparison(list[i], elem) == 0)
                            {
                                return i;
                            }
                        }
                        else
                        {
                            int j = _r.Next(i, k);
                            int r = _comparison(elem, list[j]);
                            if (r == 0)
                            {
                                return j;
                            }
                            if (r > 0)
                            {
                                return f(j + 1, k);
                            }
                            return f(i, j);

                        }
                        return -1;
                    };
            return f(0, list.Count);
        }

    }
}
